// https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iv/

// 题干：给你一个整数数组 prices 和一个整数 k ，其中 prices[i] 是某支给定的股票在第 i 天的价格。
//      设计一个算法来计算你所能获取的最大利润。
//      你最多可以完成 k 笔交易。也就是说，你最多可以买 k 次，卖 k 次。
//      注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

// 示例：输入：k = 2, prices = [2,4,1]
//      输出：2

// 碎语：同股票三原理一样，只要把2改为k即可

#include <bits/stdc++.h>
using namespace std;

class Solution
{
public:
    const int INF = 0x3f3f3f3f;
    int maxProfit(int k, vector<int>& prices)
    {
        int n = prices.size();
        vector<vector<int>> f(n, vector<int>(k + 1, -INF));
        auto g = f;
        f[0][0] = -prices[0], g[0][0] = 0;

        for (int i = 1 ; i < n ; i++){
            for (int j = 0 ; j <= k ; j++){
                f[i][j] = max(f[i - 1][j], g[i - 1][j] - prices[i]);
                g[i][j] = g[i - 1][j];
                if (j >= 1) g[i][j] = max(g[i][j], f[i - 1][j - 1] + prices[i]);
            }
        }
        int ret = 0;
        for (int j = 0 ; j <= k ; j++){
            ret = max(ret, g[n - 1][j]);
        }

        return ret;
    }
};

int main()
{
    Solution sol;
    vector<int> prices = {2,4,1};

    cout << sol.maxProfit(2, prices) << endl;

    return 0;
}